package com.lw.leetcode.back.b;

/**
 * Created with IntelliJ IDEA.
 * c
 * linked
 * 2556. 二进制矩阵中翻转最多一次使路径不连通
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/6 16:02
 */
public class IsPossibleToCutPath {

    public static void main(String[] args) {
        IsPossibleToCutPath test = new IsPossibleToCutPath();

//        int a = 300;
//        int b = 300;
//        int[][] arr = Utils.getArr(a, b, 0, 2);
//        arr[0][0] = 1;
//        arr[a - 1][b - 1] = 1;

        // true
//        int[][] arr = {{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 1}};

        // true
//        int[][] arr = {{1, 1, 1}, {1, 0, 0}, {1, 1, 1}};

        // false
//        int[][] arr = {{1,1,1}, {1,0,1}, {1,1,1}};

        // true
//        int[][] arr = {
//                {1, 1, 0, 1, 1, 1},
//                {1, 1, 1, 1, 0, 1},
//                {1, 1, 1, 1, 1, 1}};

        // true
        int[][] arr = {
                {1, 1, 1, 0, 0},
                {1, 0, 1, 0, 0},
                {1, 1, 1, 1, 1},
                {0, 0, 1, 1, 1},
                {0, 0, 1, 1, 1}};

        boolean possibleToCutPath = test.isPossibleToCutPath(arr);
        System.out.println(possibleToCutPath);

    }

    private int m;
    private int n;
    private int[][] grid;
    private int[] counts;

    public boolean isPossibleToCutPath(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        if (m == 1 && (n == 1 || n == 2)) {
            return false;
        }
        if (m == 2 && n == 1) {
            return false;
        }
        int l = m + n - 2;
        this.counts = new int[l];
        int t = find(0, 0);
        if (t == 0) {
            return true;
        }
        for (int i = 1; i < l; i++) {
            if (counts[i] > 0) {
                return true;
            }
        }
        return false;
    }

    private int find(int x, int y) {
        if (x == m - 1 && y == n - 1) {
            return 1;
        }
        if (x == m || y == n || x < 0 || y < 0) {
            return 0;
        }
        if (grid[x][y] == 0) {
            return 0;
        }
        if (grid[x][y] > 1) {
            return grid[x][y];
        }
        int b1 = find(x, y + 1);
        int b2 = find(x + 1, y);
        if (b1 == 0 && b2 == 0) {
            grid[x][y] = 0;
            return 0;
        }
        grid[x][y] = Math.max(b1, b2) + 1;
        int t = (x << 16) + y;
        if (counts[x + y] == 0) {
            counts[x + y] = t;
        } else if (counts[x + y] != t) {
            counts[x + y] = -1;
        }
        return Math.max(b1, b2) + 1;
    }

}
